﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tin
{
    class Tin
    {
        private List<TPoint> _points;
        private List<TPoint> _mini_rec;

        public Tin(List<TPoint> points)
        {
            _points = points;
        }

        /// <summary>
        /// 提取整个数据区域的最小外接矩形，作为最简单的凸包
        /// </summary>
        private void ConstructMiniRec()
        {
            _mini_rec = new List<TPoint>();
            double[] Xs = new double[_points.Count];
            double[] Ys = new double[_points.Count];
            for (int i = 0; i < _points.Count; i++)
            {
                Xs[i] = _points[i].X;
                Ys[i] = _points[i].Y;
            }
            double Xmin, Xmax, Ymin, Ymax;
            Xmin = Xs.Min();
            Xmax = Xs.Max();
            Ymax = Ys.Max();
            Ymin = Ys.Min();
            _mini_rec.Add(new TPoint { Name = "P1", X = Xmin - 1, Y = Ymin - 1 });
            _mini_rec.Add(new TPoint { Name = "P2", X = Xmin - 1, Y = Ymax + 1 });
            _mini_rec.Add(new TPoint { Name = "P3", X = Xmax + 1, Y = Ymax + 1 });
            _mini_rec.Add(new TPoint { Name = "P4", X = Xmax + 1, Y = Ymin - 1 });
        }

        /// <summary>
        /// 生成初始三角网
        /// </summary>
        /// <returns></returns>
        private List<TTriangle> ConstructInitTrinet()
        {
            List<TTriangle> initTrinet = new List<TTriangle>
            {
                new TTriangle{Point1 = _mini_rec[0], Point2 = _mini_rec[1], Point3 = _mini_rec[2] },
                new TTriangle{Point1 = _mini_rec[0], Point2 = _mini_rec[2], Point3 = _mini_rec[3] },
            };
            return initTrinet;
        }

        /// <summary>
        /// 通过遍历离散点，生成平面三角网
        /// </summary>
        /// <returns></returns>
        private List<TTriangle> ConstructTrinet()
        {
            List<TTriangle> trinet = ConstructInitTrinet();
            List<TTriangle> tempTrinet = new List<TTriangle>();
            List<TEdge> edges = new List<TEdge>();

            for (int i = 0; i < _points.Count; i++)
            {
                for (int j = 0; j < trinet.Count; j++)
                {
                    double x0, y0, r;
                    ComputeCircle(trinet[j], out x0, out y0, out r);
                    double lr = Math.Sqrt((_points[i].X - x0) * (_points[i].X - x0) + (_points[i].Y - y0) * (_points[i].Y - y0));
                    if (lr < r)
                    {
                        tempTrinet.Add(trinet[j]);
                        trinet.RemoveAt(j);
                        j--;
                    }
                }

                for (int k = 0; k < tempTrinet.Count; k++)
                {
                    edges.Add(tempTrinet[k].Edge1);
                    edges.Add(tempTrinet[k].Edge2);
                    edges.Add(tempTrinet[k].Edge3);
                }

                //删除edges中的公共边
                for (int k = 0; k < edges.Count - 1; k++)
                {
                    int sss = 0;
                    for (int m = k + 1; m < edges.Count; m++)
                    {
                        if (edges[m] == edges[k])
                        {
                            sss = 1;
                            edges.RemoveAt(m);
                            m--;
                        }
                    }
                    if (sss == 1)
                    {
                        edges.RemoveAt(k);
                        k--;
                    }
                }

                tempTrinet.Clear();

                for (int k = 0; k < edges.Count; k++)
                {
                    trinet.Add(new TTriangle { Point1 = _points[i], Point2 = edges[k].PStart, Point3 = edges[k].PEnd });
                }
                edges.Clear();
            }

            return trinet;
        }

        /// <summary>
        /// 计算三角形的外接圆
        /// </summary>
        /// <param name="triangle"></param>
        /// <param name="x0"></param>
        /// <param name="y0"></param>
        /// <param name="r"></param>
        private void ComputeCircle(TTriangle triangle, out double x0, out double y0, out double r)
        {
            double x1 = triangle.Point1.X;
            double y1 = triangle.Point1.Y;
            double x2 = triangle.Point2.X;
            double y2 = triangle.Point2.Y;
            double x3 = triangle.Point3.X;
            double y3 = triangle.Point3.Y;

            x0 = ((y2 - y1) * (y3 * y3 - y1 * y1 + x3 * x3 - x1 * x1) - (y3 - y1) * (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1))
                / (2 * (x3 - x1) * (y2 - y1) - 2 * (x2 - x1) * (y3 - y1));
            y0 = ((x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) - (x3 - x1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1))
                / (2 * (y3 - y1) * (x2 - x1) - 2 * (y2 - y1) * (x3 - x1));
            r = Math.Sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
        }

        /// <summary>
        /// 构成不规则三角网
        /// </summary>
        /// <param name="triangles"></param>
        /// <returns></returns>
        private List<TTriangle> ConstructFinalTrient(List<TTriangle> triangles)
        {
            for (int i = 0; i < triangles.Count; i++)
            {
                TTriangle triangle = triangles[i];
                for (int j = 0; j < _mini_rec.Count; j++)
                {
                    if (triangle.Point1 == _mini_rec[j] || triangle.Point2 == _mini_rec[j] || triangle.Point3 == _mini_rec[j])
                    {
                        triangles.RemoveAt(i);
                        i--;
                        break;
                    }
                }
            }
            return triangles;
        }

        /// <summary>
        /// 获取TIN
        /// </summary>
        /// <returns></returns>
        public List<TTriangle> GetTin()
        {
            // 计算外包矩形
            ConstructMiniRec();
            // 构建初始三角网
            List<TTriangle> trinet = ConstructTrinet();
            // 按一定约束过滤三角网并输出
            return ConstructFinalTrient(trinet);
        }
    }
}
